package checker.algorithms.sort;

import java.util.Arrays;

public abstract class BaseMerge extends SortBase {

    static Comparable[] aux;

    @Override
    public void sort(Comparable[] a) {

    }

    // 递归排序
    public abstract void sort(Comparable[] a, int lo, int hi);

    // 合并数组
    private static void merge(Comparable[] a, int lo, int hi) {
        aux = new Comparable[a.length];

        for (int i = 0; i < a.length; i++) {
            aux[i] = a[i];
        }


        int mid = (lo + hi) / 2 + 1;
        int i = lo, j = mid;

        for (int k = lo; k <= hi; k++) {

            if (i > mid) {
                // i>mid即前部分已经遍历完，值全取j（后部分）
                a[k] = aux[j++];
            } else if (j > hi) {
                // 后部分遍历结束，值全取前部分
                a[k] = aux[i++];
            } else {
                if (less(aux[i], aux[j])) {
                    // i小取i
                    a[k] = aux[i++];
                } else {
                    // j小取j
                    a[k] = aux[j++];
                }
            }
        }

    }

    public static void main(String[] args) {
        Integer[] a = {1, 2, 3, 5, 9, 2, 4, 5, 7, 8};
        merge(a, 5, a.length - 1);

        System.out.println(Arrays.toString(a));
        System.out.println(isSorted(a));
    }
}
